package sorting;

import util.ArrayUtil;
import util.Tracer;

public class RadixSortInPlace {
	public static void sort(int[] numbers, int from, int to, int radix)
	{
		if(from == to) return;

		int part = from;
		for(int i = from; i <= to; i ++)
		{
			int digit = numbers[i] >> radix & 1;
			if(digit == 0)
				ArrayUtil.each(numbers, part ++, i);
		}

		if(radix != 0)
		{
			sort(numbers, from, part - 1, radix - 1);
			sort(numbers, part, to, radix - 1);
		}
	}
	
	public static void main(String[] args) {
		int[] numbers = {8, 7, 5, 7, 2, 4, 4, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 2};
		sort(numbers, 0, numbers.length - 1, 3);
		
		Tracer.trace(numbers);
	}
}
